Micron Document
<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>LLL-Algorithmus</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/LLL-Algorithmus"> <link href="./_mw_/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-LLL-Algorithmus rootpage-LLL-Algorithmus skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">LLL-Algorithmus</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>LLL-Algorithmus</b> ist ein nach <a href="Arjen_Lenstra" title="Arjen Lenstra">Arjen Lenstra</a>, <a href="Hendrik_Lenstra" title="Hendrik Lenstra">Hendrik Lenstra</a> und <a href="L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">László Lovász</a> benannter, 1982 veröffentlichter <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, der für ein <a href="Gitter_(Mathematik)" title="Gitter (Mathematik)">Gitter</a> eine Basis aus möglichst kurzen Vektoren berechnet. Diese <a href="Vektor" title="Vektor">Vektoren</a> sind <a href="Approximation" title="Approximation">Approximationen</a> für die kürzesten voneinander linear unabhängigen Vektoren des Gitters. Bei seiner Entdeckung war der LLL-Algorithmus der erste effiziente Gitterreduktionsalgorithmus.
</p>

<div class="mw-heading mw-heading2"><h2 id="Kurze_Gittervektoren">Kurze Gittervektoren</h2></div>
<p>Eine Gitterbasis lässt sich als Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=[b_{1},\dots ,b_{n}]\in \mathbb {R} ^{m}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
<mo>=</mo>
<mo stretchy="false">[</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">]</mo>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B=[b_{1},\dots ,b_{n}]\in \mathbb {R} ^{m}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/465cb6d1d6a9f79693e1ef4bf97ac1f40fdcc8f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.796ex; height:2.843ex;" alt="{\displaystyle B=[b_{1},\dots ,b_{n}]\in \mathbb {R} ^{m}}" loading="lazy"></span> angeben. Der kürzeste Gittervektor minimiert die <a href="Vektornorm" class="mw-redirect" title="Vektornorm">Norm</a> des Vektors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle \sum _{i=1}^{n}t_{i}b_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mstyle displaystyle="false" scriptlevel="0">
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</munderover>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \textstyle \sum _{i=1}^{n}t_{i}b_{i}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2bf919a8e1f89eb3a8a44110636310304627c68c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.178ex; height:3.176ex;" alt="{\displaystyle \textstyle \sum _{i=1}^{n}t_{i}b_{i}}" loading="lazy"></span>, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{1},\dots ,t_{n}\in \mathbb {Z} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle t_{1},\dots ,t_{n}\in \mathbb {Z} }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e787c488b2323f24d511ce7f44061237f4166bfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.521ex; height:2.509ex;" alt="{\displaystyle t_{1},\dots ,t_{n}\in \mathbb {Z} }" loading="lazy"></span> nicht alle gleich 0 sind. Der LLL-Algorithmus führt diese Minimierung bezüglich der <a href="Euklidische_Norm" title="Euklidische Norm">euklidischen Norm</a> durch.
</p>
<div class="mw-heading mw-heading2"><h2 id="LLL-Basen">LLL-Basen</h2></div>
<div class="mw-heading mw-heading3"><h3 id="Definition">Definition</h3></div>
<p>Üblicherweise werden LLL-Basen über ihre <a href="QR-Zerlegung" title="QR-Zerlegung">QR-Zerlegung</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=QR}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
<mo>=</mo>
<mi>Q</mi>
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B=QR}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68ece4ef8e16ca43da3735bc9bc6e36ba80ffbd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.465ex; height:2.509ex;" alt="{\displaystyle B=QR}" loading="lazy"></span> definiert. Eine LLL-Basis <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=QR}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
<mo>=</mo>
<mi>Q</mi>
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B=QR}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68ece4ef8e16ca43da3735bc9bc6e36ba80ffbd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.465ex; height:2.509ex;" alt="{\displaystyle B=QR}" loading="lazy"></span> zum Reduktionsfaktor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta \in \left[{\frac {1}{4}},1\right]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>δ<!-- δ --></mi>
<mo>∈<!-- ∈ --></mo>
<mrow>
<mo>[</mo>
<mrow>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>1</mn>
<mn>4</mn>
</mfrac>
</mrow>
<mo>,</mo>
<mn>1</mn>
</mrow>
<mo>]</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \delta \in \left[{\frac {1}{4}},1\right]}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3d38ecd2515f66a2358692f39e23701ac669c779.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:10.539ex; height:6.176ex;" alt="{\displaystyle \delta \in \left[{\frac {1}{4}},1\right]}" loading="lazy"></span> wird über folgende zwei Eigenschaften definiert:
</p>
<ol><li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2|r_{i,j}|\leq r_{j,j},1\leq j<i\leq n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<msub>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mo>≤<!-- ≤ --></mo>
<msub>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>j</mi>
<mo>,</mo>
<mi>j</mi>
</mrow>
</msub>
<mo>,</mo>
<mn>1</mn>
<mo>≤<!-- ≤ --></mo>
<mi>j</mi>
<mo>&lt;</mo>
<mi>i</mi>
<mo>≤<!-- ≤ --></mo>
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2|r_{i,j}|\leq r_{j,j},1\leq j&lt;i\leq n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d81af2866c1b7bb780a9c3567caf5471e53b9f80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.278ex; height:3.009ex;" alt="{\displaystyle 2|r_{i,j}|\leq r_{j,j},1\leq j<i\leq n}" loading="lazy"></span> (Längenreduktion),</li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta r_{i,i}^{2}\leq r_{i+1,i}^{2}+r_{i+1,i+1}^{2},1\leq i<n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>δ<!-- δ --></mi>
<msubsup>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>,</mo>
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msubsup>
<mo>≤<!-- ≤ --></mo>
<msubsup>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
<mo>,</mo>
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msubsup>
<mo>+</mo>
<msubsup>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
<mo>,</mo>
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msubsup>
<mo>,</mo>
<mn>1</mn>
<mo>≤<!-- ≤ --></mo>
<mi>i</mi>
<mo>&lt;</mo>
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \delta r_{i,i}^{2}\leq r_{i+1,i}^{2}+r_{i+1,i+1}^{2},1\leq i&lt;n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/77a896cbd9526cd817df7cdf65ee589847601526.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:32.499ex; height:3.509ex;" alt="{\displaystyle \delta r_{i,i}^{2}\leq r_{i+1,i}^{2}+r_{i+1,i+1}^{2},1\leq i<n}" loading="lazy"></span> (LLL-Eigenschaft)</li></ol>
<p>Dabei sind <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i,j}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle r_{i,j}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ff99789d445d710aa4b4f8868f4e58acd7fc230e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.983ex; height:2.343ex;" alt="{\displaystyle r_{i,j}}" loading="lazy"></span> die Einträge der Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span>. Es wird angenommen, dass die QR-Zerlegung von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> so durchgeführt wird, dass die <a href="Hauptdiagonale" title="Hauptdiagonale">Hauptdiagonale</a> von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> keine negativen Elemente enthält.
</p><p>Der Reduktionsfaktor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>δ<!-- δ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"></span> gibt die Stärke der Reduktion an: Je näher er an 1 liegt, desto kürzer sind die Vektoren der reduzierten Basis. Für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta =1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>δ<!-- δ --></mi>
<mo>=</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \delta =1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30c5c1a63ccd876384e6cf0a31296e3aee31ac84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle \delta =1}" loading="lazy"></span> ist nicht bekannt, ob es einen effizienten Algorithmus gibt.
</p>
<div class="mw-heading mw-heading3"><h3 id="Eigenschaften">Eigenschaften</h3></div>
<p>LLL-reduzierte Basen approximieren die kürzesten Vektoren mit einem Approximationsfaktor, der exponentiell in der Anzahl der Vektoren ist. Im Folgenden sei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha :={\tfrac {1}{\delta -{\frac {1}{4}}}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>α<!-- α --></mi>
<mo>:=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mfrac>
<mn>1</mn>
<mrow>
<mi>δ<!-- δ --></mi>
<mo>−<!-- − --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>1</mn>
<mn>4</mn>
</mfrac>
</mrow>
</mrow>
</mfrac>
</mstyle>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \alpha :={\tfrac {1}{\delta -{\frac {1}{4}}}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/02862593c24e06a60d926690d6d46230312c3093.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:9.593ex; height:5.176ex;" alt="{\displaystyle \alpha :={\tfrac {1}{\delta -{\frac {1}{4}}}}}" loading="lazy"></span>. Offensichtlich ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha \geq {\tfrac {4}{3}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>α<!-- α --></mi>
<mo>≥<!-- ≥ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mfrac>
<mn>4</mn>
<mn>3</mn>
</mfrac>
</mstyle>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \alpha \geq {\tfrac {4}{3}}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c02e697dfff4871886d607fec29bfcfbf769bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:6.244ex; height:3.676ex;" alt="{\displaystyle \alpha \geq {\tfrac {4}{3}}}" loading="lazy"></span>. Der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te LLL-reduzierte Vektor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle b_{i}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/40a8c2db2990a53c683e75961826167c5adac7c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.797ex; height:2.509ex;" alt="{\displaystyle b_{i}}" loading="lazy"></span> approximiert das <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te <i>sukzessive Minimum</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>λ<!-- λ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/72fde940918edf84caf3d406cc7d31949166820f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.155ex; height:2.509ex;" alt="{\displaystyle \lambda _{i}}" loading="lazy"></span> auf folgende Weise: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {||b_{i}||^{2}}{\lambda _{i}^{2}}}\leq \alpha ^{n-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mfrac>
<mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<msub>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
</mrow>
<msubsup>
<mi>λ<!-- λ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msubsup>
</mfrac>
</mstyle>
</mrow>
<mo>≤<!-- ≤ --></mo>
<msup>
<mi>α<!-- α --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\tfrac {||b_{i}||^{2}}{\lambda _{i}^{2}}}\leq \alpha ^{n-1}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce8092d91d7b5790daa1f20f24872e6471dcec15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:12.733ex; height:5.509ex;" alt="{\displaystyle {\tfrac {||b_{i}||^{2}}{\lambda _{i}^{2}}}\leq \alpha ^{n-1}}" loading="lazy"></span>, wobei das <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te sukzessive Minimum die Länge des <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-ten kürzesten Vektors ist, der von keiner Menge kürzerer Vektoren linear abhängig ist.
</p>
<div class="mw-heading mw-heading2"><h2 id="Algorithmus">Algorithmus</h2></div>
<ol><li>Berechne die erste Spalte von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span>.</li>
<li>Setze <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k:=2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>:=</mo>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k:=2}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3b762804be7d92cb4f11ba7d96a8497168893a78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.119ex; height:2.176ex;" alt="{\displaystyle k:=2}" loading="lazy"></span> (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> ist die Spalte, die gerade bearbeitet werden soll; die ersten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy"></span> Spalten sind immer LLL-reduziert)</li>
<li>Solange <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\leq n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>≤<!-- ≤ --></mo>
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k\leq n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/621f658bb51d7caac329d29e9bf435361813777f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.704ex; height:2.343ex;" alt="{\displaystyle k\leq n}" loading="lazy"></span> wiederhole: Berechne die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-te Spalte von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span>, längenreduziere sie (Algorithmus siehe unten). Prüfe, ob die LLL-Eigenschaft für die Spalten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> erfüllt ist.</li>
<li>Falls ja: Setze <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k:=k+1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>:=</mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k:=k+1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7734722b79382d4aa24c964bb94b49c1b7d5a2ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.171ex; height:2.343ex;" alt="{\displaystyle k:=k+1}" loading="lazy"></span></li>
<li>Falls nein: Vertausche Spalten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>, setze <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k:=\max(k-1,2)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>:=</mo>
<mo movablelimits="true" form="prefix">max</mo>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k:=\max(k-1,2)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d2868833b867a8f948a4fd2a394a7111f7bde1ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.502ex; height:2.843ex;" alt="{\displaystyle k:=\max(k-1,2)}" loading="lazy"></span>.</li></ol>
<p>Der Algorithmus folgt unmittelbar aus der Definition: Erzwinge Spalte für Spalte, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> eine LLL-Basis ist. Längenreduktion lässt sich leicht herbeiführen. Lediglich die LLL-Eigenschaft ist kompliziert, weil sie indirekt weit voneinander entfernte Spalten in Beziehung bringt. Darum ist es nötig, Spalten zu vertauschen und wieder einen Schritt zurückzugehen.
</p>
<div class="mw-heading mw-heading2"><h2 id="Längenreduktion"><span id="L.C3.A4ngenreduktion"></span>Längenreduktion</h2></div>
<p>Die Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> ist eine obere <a href="Dreiecksmatrix" title="Dreiecksmatrix">Dreiecksmatrix</a> mit positiver Diagonale. Ziel der Längenreduktion ist es, alle Nicht-Diagonalelemente möglichst (betragsmäßig) klein zu machen, ohne das Gitter zu verändern. Jede Zeile von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> hat folgenden Aufbau: null oder mehr Nullen, das Diagonalelement, null oder mehr weitere Elemente. Dabei besitzen die Nullen schon den kleinstmöglichen Betrag. Die LLL-Eigenschaft sorgt dafür, dass das Diagonalelement nicht allzu groß sein kann. Die Längenreduktion bewirkt nun für alle folgenden Elemente, dass sie betragsmäßig höchstens halb so groß wie das Diagonalelement sind. Das lässt sich dadurch herbeiführen, dass für jedes zu große Nicht-Diagonalelement die Spalte, die das entsprechende Diagonalelement enthält, so oft addiert oder subtrahiert wird, bis das zu große Element betragsmäßig minimal ist. Der folgende Algorithmus längenreduziert die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-te Spalte von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span>:
</p>
<ol><li>Für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=k-1,\dots ,1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
<mo>=</mo>
<mi>k</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i=k-1,\dots ,1}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a69d19a18595e632713c816b136b7039f9a9ffb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.456ex; height:2.509ex;" alt="{\displaystyle i=k-1,\dots ,1}" loading="lazy"></span> wiederhole:</li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{i}:=R_{i}-\left[{\frac {r_{i,k}}{r_{k,k}}}\right]R_{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>:=</mo>
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<mrow>
<mo>[</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<msub>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>,</mo>
<mi>k</mi>
</mrow>
</msub>
<msub>
<mi>r</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
<mo>,</mo>
<mi>k</mi>
</mrow>
</msub>
</mfrac>
</mrow>
<mo>]</mo>
</mrow>
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R_{i}:=R_{i}-\left[{\frac {r_{i,k}}{r_{k,k}}}\right]R_{k}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0b61937de69e664b8e1f7b12af2fdb4c93eef34e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:21.695ex; height:6.176ex;" alt="{\displaystyle R_{i}:=R_{i}-\left[{\frac {r_{i,k}}{r_{k,k}}}\right]R_{k}}" loading="lazy"></span></li></ol>
<p>Dabei ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R_{i}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db421291be9d0103404ced7495b363437b67b6b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.564ex; height:2.509ex;" alt="{\displaystyle R_{i}}" loading="lazy"></span> der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te Spaltenvektor von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\cdot ]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">[</mo>
<mo>⋅<!-- ⋅ --></mo>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle [\cdot ]}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/41b4e841c71afe1890198191aab15bc225bbc0b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.941ex; height:2.843ex;" alt="{\displaystyle [\cdot ]}" loading="lazy"></span> die Rundungsfunktion, die auf die nächste <a href="Ganze_Zahl" title="Ganze Zahl">ganze Zahl</a> rundet. Es ist wichtig, dass Schritt 2. mit fallendem und nicht mit steigendem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> ausgeführt wird.
</p>
<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>
<p>Eine erste hervorragende Anwendung erhielt der LLL-Algorithmus 1984 bei der Widerlegung der mit der <a href="Riemannsche_Vermutung" title="Riemannsche Vermutung">Riemannschen Vermutung</a> zusammenhängenden <a href="Riemannsche_Vermutung#Varianten_und_Verallgemeinerungen" title="Riemannsche Vermutung">Mertensschen Vermutung</a> durch <a href="Andrew_Odlyzko" title="Andrew Odlyzko">Andrew Odlyzko</a> und <a href="Herman_te_Riele" title="Herman te Riele">Herman te Riele</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Dabei wurde ein Gitter der Dimension 70 konstruiert und seine Basis reduziert, das es erlaubte, ein Problem der mehrdimensionalen inhomogenen <a href="Diophantische_Approximation" title="Diophantische Approximation">diophantischen Approximation</a> mit ausgewählten nichttrivialen Nullstellen der <a href="Riemannsche_%CE%B6-Funktion" class="mw-redirect" title="Riemannsche ζ-Funktion">Riemannschen Zetafunktion</a> näherungsweise zu lösen.
2006 wurde die Berechnung an Gittern der Dimension um 100 wiederholt und die Ergebnisse verbessert.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p><p>Der Algorithmus findet Anwendung in vielen Bereichen, teilweise in modifizierter Version. Er lässt sich auch auf zum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} ^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">Z</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} ^{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a9b5de7ced4588982b574fe19894aec6a3ca4c49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.769ex; height:2.343ex;" alt="{\displaystyle \mathbb {Z} ^{n}}" loading="lazy"></span> isometrisch isomorphen Gittern anwenden, wobei die Reduktion dann bezüglich des dortigen Skalarprodukts durchgeführt wird. Ein eher unerwartetes Beispiel hierfür ist der Algorithmus von Unger<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> aus der <a href="Gruppentheorie" title="Gruppentheorie">Gruppentheorie</a>, der zum Finden von irreduziblen <a href="Charakter_(Mathematik)" title="Charakter (Mathematik)">Charakteren</a> einer Gruppe verwendet wird.
</p><p>Da in bestimmten Anwendungen des Algorithmus die anfangs vorliegenden Basisvektoren eine außerordentliche Länge aufweisen können, wurde angestrebt, seine Laufzeit in Abhängigkeit von dieser Länge zu verringern. Es wurden Varianten entwickelt, die eine quadratische Zeitkomplexität bezüglich der Bitlänge der Ausgangsdaten<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> oder sogar nahezu lineare Komplexität<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> besitzen.
</p>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li><a href="Arjen_Lenstra" title="Arjen Lenstra">A. K. Lenstra</a>, <a href="Hendrik_Lenstra" title="Hendrik Lenstra">H. W. Lenstra, Jr.</a>, <a href="L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">L. Lovász</a>: <cite style="font-style:italic">Factoring polynomials with rational coefficients</cite>. In: <cite style="font-style:italic">Mathematische Annalen</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em">&nbsp;</span>261</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em">&nbsp;</span>4</span>, 1982, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em">&nbsp;</span>515–534</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01457454">10.1007/BF01457454</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&amp;rfr_id=info:sid/de.wikipedia.org:LLL-Algorithmus&amp;rft.atitle=Factoring+polynomials+with+rational+coefficients&amp;rft.au=A.+K.+Lenstra%2C+H.+W.+Lenstra%2C+Jr.%2C+...&amp;rft.date=1982&amp;rft.doi=10.1007%2FBF01457454&amp;rft.genre=journal&amp;rft.issue=4&amp;rft.jtitle=Mathematische+Annalen&amp;rft.pages=515-534&amp;rft.volume=261" style="display:none">&nbsp;</span></li>
<li>Phong Q. Nguyen, Brigitte Valée (Hrsg.): <i>The LLL algorithm. Survey and applications.</i> Springer 2010, ISBN 978-3-642-02294-4.</li>
<li>Murray R. Bremner: <i>Lattice basis reduction: An introduction to the LLL algorithm and its applications.</i> CRC Press 2011, ISBN 978-1-439-80702-6.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>
<ul><li><a rel="nofollow" class="external text" href="https://www.uni-frankfurt.de/102692734/gitter.pdf"><i>Gitter und Kryptographie</i></a> (PDF; 1015&nbsp;KB). <a href="Johann_Wolfgang_Goethe-Universit%C3%A4t_Frankfurt_am_Main" title="Johann Wolfgang Goethe-Universität Frankfurt am Main">Johann Wolfgang Goethe-Universität</a> Frankfurt am Main, 17. Oktober 2011 (Skript für die Vorlesungen von Prof. C. P. Schnorr, Wintersemester 2010)</li>
<li>Phong Q. Nguyen: <a rel="nofollow" class="external text" href="http://www.di.ens.fr/~pnguyen/SLIDES/CHINACRYPT-LATTICES.html"><i>Lattice reduction algorithms: Theory and practice.</i></a> eingeladener Powerpoint-Vortrag zur EUROCRYPT'11-Konferenz</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>
<ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><a href="Andrew_Odlyzko" title="Andrew Odlyzko">A. M. Odlyzko</a>, <a href="Herman_te_Riele" title="Herman te Riele">H. J. J. te Riele</a>: <i><style data-mw-deduplicate="TemplateStyles:r261891140">
/* start https://de.wikipedia.org/ */


.mw-parser-output .webarchiv-memento a{color:inherit}


/* end https://de.wikipedia.org/ */
</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20130216174731/http://oai.cwi.nl/oai/asset/1823/1823A.pdf">Disproof of the Mertens conjecture.</a> (<span class="webarchiv-memento"><a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a></span> vom 16. Februar 2013 im </i><a href="Internet_Archive" title="Internet Archive">Internet Archive</a><i>)</i> J. reine angew. Math. 357 (1985), S. 138–160</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">T. Kotnik, H. J. J. te Riele: <i>Mertens conjecture revisited.</i> ANTS 7 (Lecture Notes Computer Science 4076) (2006), S. 156–167</span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">William R. Unger: <i>Computing the character table of a finite group</i>, Journal of Symbolic Computation 41 (2006) No. 8, 847–862</span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">Phong Q. Nguyen, Damien Stehlé: <i><a rel="nofollow" class="external text" href="ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf">An LLL algorithm with quadratic complexity.</a><span style="display:none"><a rel="nofollow" class="external text" href="http://deadurl.invalid/ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf">@1</a></span><span style="display:none"><a rel="nofollow" class="external text" href="ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf">@2</a></span><span style="display:none">Vorlage:Toter Link/ftp.di.ens.fr</span> <small>(Seite nicht mehr abrufbar, festgestellt im November 2022. <a rel="nofollow" class="external text" href="http://timetravel.mementoweb.org/list/2010/ftp://ftp.di.ens.fr/pub/users/pnguyen/FullL2.pdf">Suche in Webarchiven</a>)</small></i>
SIAM J. Comput. 39 (2009) Nr. 3, S. 874–903</span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">Andrew Novocin, Damien Stehlé, Gilles Villard: <i><a rel="nofollow" class="external text" href="http://hal.archives-ouvertes.fr/docs/00/53/48/99/PDF/L1-hal.pdf">An LLL-reduction algorithm with quasi-linear time complexity.</a></i> STOC 2011 (<i>Symposium on Theory of Computing</i>), S. 403–412</span>
</li>
</ol></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-04-05" href="https://de.wikipedia.org/wiki/?title=LLL-Algorithmus&amp;oldid=254885999">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>

</body></html>